The present invention relates to a field of radio frequency tag identification. More specifically, the present invention relates to a method for resolving contention in identification of a plurality of radio frequency tags.
The object of any Radio Frequency Identifications (xe2x80x9cRF IDxe2x80x9d) system is to carry data in suitable transponders, generally known as tags, and to retrieve data, by machine-readable means, at a suitable time and place to satisfy particular application needs. The word xe2x80x9ctransponderxe2x80x9d, derived from TRANSmitter/resPONDER, reveals the function of a tag, which usually responds to a transmitted request or a communicated request for data it carries. The data in the tag may provide identification information for an item, a location, an identity of a vehicle, an animal, a person or other information.
Radio frequency identification systems are typically categorized as either xe2x80x9cactivexe2x80x9d or xe2x80x9cpassivexe2x80x9d. In an active RF ID system, tags are powered by an internal battery, and data written into active tags may be rewritten and modified. In a passive RF ID system, tags operate without an internal power source and are usually programmed with a unique set of data that cannot be modified. A typical passive RF ID system comprises two components: an interrogator (reader) and a plurality of passive tags. The main component of every passive RF ID system is a plurality of information carrying tags that respond to a coded RF signals that are typically sent from the reader.
A passive tag typically includes an antenna and a semiconductor chip comprising radio frequency (xe2x80x9cRFxe2x80x9d) circuitry, logic and a non-volatile memory unit. Further, a time-varying electromagnetic RF signal (carrier signal) that is typically transmitted by a reader located at a base station energizes the passive tag. The reader usually comprises a microcontroller-based unit with a wound output coil and detector hardware. In a typical configuration, in addition to the reader, the base station comprises an antenna, an RF transmitter and an RF receiver. The reader may issue commands to the RF transmitter and receive commands from the RF receiver. The commands may serve to identify a plurality of tags present in a reader""s field of view. The size of the reader""s field of view depends primarily on a power level of the RF signal transmitted from the reader.
The RF transmitter at the base station may, for instance, encode a command from the reader, modulate the command to a radio frequency signal and, then, pass it to the antenna located at the base station. The RF receiver at the base station may receive, demodulate and pass to the reader return signals from the plurality of RF tags in the reader""s field of view.
As known in the art, a passive tag is not a transmitter, yet a bi-directional communication is taking place in passive RF ID systems. The passive tag may employ a process called a backscatter modulation to send data to a reader. In a typical system, the reader continuously generates an RF carrier sine wave and senses for occurrences of a modulation, which would indicate a presence of a tag in a reader""s field of view. When a tag enters the reader""s field of view and, further, receives sufficient energy to operate, the tag typically divides down the RF carrier sine wave and, subsequently, starts clocking out identification data from a non-volatile memory unit, such as programmable registers.
The tag may clock out the identification data to an output transistor, which is typically connected to the tag""s input coils. Consequently, the tag""s output transistor may sequentially shunt the coil correspondingly to data that is clocked out from the non-volatile memory unit. Shunting the coil causes a momentary fluctuation of the carrier wave, which results in a slight change in an amplitude of the carrier wave and, thus, the reader may peak-detect the amplitude-modulated data and process the resulting bitstream according to encoding and modulation methods used in a particular RF ID system. This amplitude-modulation loading of the reader""s transmitted field provides a communication path back to the reader.
In a modem business, maintaining an accurate inventory of merchandise is crucial. For instance, in a rental video store, a tag could be attached to each video tape in the video store, and one or more readers could then be used to maintain an inventory of video tapes. Further, it is often crucial to quickly determine what tags are in a given area.
There are many procedures that readers in RF ID systems may use to verify identification of a plurality of tags in readers"" fields of view. In this regard, each tag in a reader""s field of view may have an associated identification value that is stored cooperatively in a number of identification registers on the tag. Typically, for example, a tag may have a 36-bit identification value that is stored in three 12-bit identification registers. Further, each tag may have a corresponding set of counters (i.e., typically, three 12-bit counters) that can be controlled by carrier signals sent from a reader. A reader may send RF instruction signals to the tags in its field of view, which may cause actions to be taken with respect to the tags"" counters and identification registers, so as to, in turn, modify the RF carrier and indicate the presence of the tags. One such instruction, for instance, may be an initialize instruction, which causes a recipient-tag to initialize a specified counter or counters. Another such instruction, for instance, may be an increment instruction, which causes a recipient-tag to increment a specified counter or counters.
According to one of the commonly used procedures for tag identification, a reader may first send an initialization instruction signal out to any tags in its field of view, directing the tags to initialize their first counters to zero. The reader may then sequentially transmit increment instructions to the tags, causing the tags to sequentially increment their first counters. Given 12 bits per register, in a typical arrangement, the reader may thus send out 4095 increment instructions.
When a count on the first counter of a tag matches a coded identification value on the tag""s associated first identification register, the tag may then be arranged to respond to the reader by shifting out its complete identification value from all of its identification registers, thereby modifying the RF carrier to indicate the presence of the tag. Further, the tag may also shift out additional bits, such as a checksum (e.g., an 8-bit checksum), for instance. In this manner, if only one tag responds to the reader, the reader may properly detect that tag""s identification and conclude that the tag is present.
However, this approach can suffer from a problem known as a contention. Contention occurs when more than one tag selects the same time slot for transmission of an identification coded value. This can occur in the process described above, for instance, if more than one tag""s first counter matches the coded value in its first identification register. As a result, more than one tag will responsively send their full identification values and checksums to the reader. When is contention occurs, the reader is simultaneously bombarded with more than one tag""s identification code and checksum in the same time slots. From the reader""s perspective, a single identification code and checksum arrives, but the checksum will not be correct. Consequently, the reader will not be able to correctly detect the identification of each responding tag.
If contention occurs in the process above, according to common practice (known as the xe2x80x9cpartial readxe2x80x9d method), the reader may keep the first counters of the tags in the field of view at the contending count (i.e., by not further incrementing the first counters) and may initiate counting on the second counters of the tags in the reader""s field of view. In turn, when (i) the first contending count matches the tag""s first identification register and (ii) a count on the tag""s second counter matches the tag""s second identification register, the tag may be arranged to respond to the reader by shifting out its complete identification value from all of its identification registers. If a contention then occurs with respect to the second counters, the reader may then similarly use the remaining counter(s) of the tags to resolve the contention. In this manner, the reader may detect identification data of all tags in the reader""s field of view.
While the partial read method provides a mechanism for resolving a contention that occurs between a plurality of tags in a reader""s field of view, the method is not particularly efficient. For example, the method can take a long time to gather all identification information of the tags in the reader""s field of view. In particular, for instance, if two tags in the field of view have the respective identification codes 4095:4095:4094 and 4095:4095:4095 (encoded in their respective three 12-bit registers), the reader may be forced to increment entirely through all three counters resolving the contention. That would mean that the tags would have to increment 212+212+212 counts on three counters associated with the registers. For applications that require quick reading of tag identification values, this amount of work is undesirable.
An exemplary embodiment of the present invention provides a more efficient method of contention resolution, employing a sort of tree-splitting algorithm. Generally speaking, for each counter for instance, the reader may first check to see whether the tags in its field of view have identification codes falling within a given range of values. If only one does, or if none do, then the reader is done with respect to that counter.
If more than one does, then the reader may repeatedly divide and test the specified range until there is no contention or until the range reaches a predetermined limit (e.g., if it gets too small). In particular, for instance, the reader may split the range in half (or in some other number of range segments) and, with respect to each half, may check to see whether the tags in its field of view have identification codes that match that half. With respect to each half in which the reader discovers a contention, the reader may in turn split the half in two again and repeat the process. In this way, the reader can quickly eliminate large sections of the counter if no tags exist in those sections.
For example, a reader may send to a plurality of tags a range-instruction signal that indicates a specified range of values of the first identification register. The instruction signal may instruct the tags to respond (i.e., to clock out their full identification values onto the RF carrier) if the value in their first identification register falls within the specified range. Each tag may thus have logic arranged to determine whether a value on a given identification register is within a specified range and, if so, to responsively transmit its identification code and a checksum.
If the reader detects an identification code and a correct checksum, the reader may conclude that only one tag has an identification value falling within the specified range. Similarly, if the reader receives no response, the reader may conclude that no tag has an identification value falling within the specified range. In either case, the reader may then proceed to perform the same process with respect to the other identification registers as well.
If a contention occurs, however, the reader may split the specified range in half, so as to produce two range segments, a lower segment and a higher segment. With respect to each range segment, the reader may then send a new range-instruction signal, indicating the range segment as the specified range. If the reader receives no response for a given range segment, the reader may efficiently eliminate that entire range segment from further consideration, focusing instead on the other range segment(s).
Each register or group of registers can be analyzed in up to any number of sub-segments. In the exemplary embodiment, for instance, each 12-bit register can be analyzed in 8 range segments each of 512 counts. With this arrangement, the reader may first check two range segments [0 to 2047] and [2048 to 4095]. In response to a contention in the range segment [0 to 2047], the reader may check the two range segments [0 to 1023] and [1024 to 2047]; and, in response to a contention in the range [2048 to 4095] the reader may then check the two range segments [2048 to 3071] and [3072 to 4095]. Continuing in this way, the reader may ultimately check the following eight range segments: [0 to 511], [512 to 1023], [1024 to 1535], [1536 to 2047], [2048 to 2559], [2560 to 3071], [3072 to 3583], and [3584 to 4095].
If the reader still has a contention in a given range segment, the reader may more readily perform the partial read method described above within the minimum sized range segment, for instance, in an effort to identify the tags in the range segment. In turn, if the reader still has a contention, the reader may then move on to analyze to the next identification register.
Thus, in one respect, an exemplary embodiment of the invention may take the form of a method for identifying a plurality of passive identification tags in a field of view, where each tag has a respective identification value, and each tag has a register value within a predetermined range. The method may involve first splitting the predetermined range into multiple first sub-ranges and then, for each first sub-range, requesting each tag whose register value falls within the first sub-range to communicate the tag""s identification value. In response to a determination that more than one tag has a register value within a given first sub-range, the method may then involve splitting the given first sub-range into multiple second sub-ranges and, for each second sub-range, requesting each tag whose register value falls within the second sub-range to communicate the tag""s identification value.
Still further, in response to a determination that more than one tag has a register value within a given second sub-range, the method may involve applying the partial read method to identify all tags whose register values fall within the given second sub-range. And yet further, in response to a determination that more than one tag has a register value within a given second sub-range, the method may involve splitting the given second sub-range into a plurality of third sub-ranges and, for each third sub-range, requesting each tag whose register value falls within the third sub-range to communicate the tag""s identification value.
Each tag may be a radio frequency identification tag, for instance. Further, each tag may, for instance, have several registers with a unique value permanently encoded in each register, and each tag""s identification value may then be defined as a combination of the tag""s respective register values.
In addition, the predetermined range may have a predetermined size, such as 4096 possible values (e.g., from 0 to 4095) for instance. Further, each of the multiple first sub-ranges may have a first size that is half of the predetermined size. Still further, each of the multiple second sub-ranges may have a second size that is half the first size, and each of the multiple third sub-ranges may have a third size that is half of the second size. Of course, other sizes are possible as well.
In another respect, an exemplary embodiment may take the form of a reader that is programmed to perform a method such as that described above. Alternatively, an exemplary embodiment may take the form of a passive identification system that includes a reader and a plurality of passive identification tags. Each tag may have a respective identification value, and each tag may have a register value within a predetermined range. The reader may be arranged to send a number of range-instructions to the tags, each indicating a search range. And each tag may be arranged to receive each range-instruction and to responsively determine whether the tag""s register value falls within the specified search range. With this arrangement, the reader may apply a recursive partitioning and searching method such as that described above.